<?php
require $root . '/QueueByLinkedList/QueueByLinkedList.php';

class AVL
{
    private $root;
    private $size;

    /**
     * 构造函数 初始化 AVL
     * BinarySearchTree constructor.
     */
    public function __construct()
    {
        $this->root = null;
        $this->size;
    }

    /**
     * 判断二叉树是否为二分搜索树
     */
    public function isBST(): bool
    {
        $queue = new QueueByLinkedList();
        $this->inOrder($this->root, $queue);
        do {
            $e = $queue->dequeue();
            if ($queue->getSize() > 0 && $e > $queue->getFront()) {
                return false;
            }
        } while ($queue->getSize() > 0);

        return true;
    }

    /**
     * 判断二叉树是否为平衡二叉树
     * @return bool
     */
    public function isBalanced(): bool
    {
        return $this->recursionIsBalanced($this->root);
    }

    /**
     * 遍历二叉树 判断每个节点是否满足平衡因子绝对值 小于等于 1
     * @param $node
     * @return bool
     */
    private function recursionIsBalanced($node)
    {
        if ($node != null) {
            if ($this->getBalanceFactor($node) < -1 || $this->getBalanceFactor($node) > 1) {
                return false;
            }
            $left = $this->recursionIsBalanced($node->left);
            $right = $this->recursionIsBalanced($node->right);

            if (!$left || !$right) {
                return false;
            }
        }

        return true;
    }

    /**
     * 中序遍历二分搜索树
     */
    private function inOrder($root, $queue)
    {
        if ($root != null) {
            $this->inOrder($root->left, $queue);
            $queue->enqueue($root->e);
            $this->inOrder($root->right, $queue);
        }
    }

    /**
     * 获取 AVL 节点的高度 h
     * @param AVLNode $node
     * @return int
     */
    private function getHeight($node)
    {
        if ($node == null) {
            return 0;
        }
        return $node->height;
    }

    /**
     * 获取当前搜索树元素个数
     * @return mixed
     */
    public function getSize()
    {
        return $this->size;
    }

    /**
     * 判断当前 AVL 是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size == 0;
    }

    /**
     * 向 AVL 添加元素
     * @param $e
     */
    public function add($e)
    {
        $this->root = $this->recursionAdd($this->root, $e);
    }

    /**
     * 递归向 AVL 添加元素
     * @param Node $root
     * @param $e
     */
    private function recursionAdd($root, $e)
    {
        if ($root == null) { //若节点为空则添加元素 并且返回当前节点信息
            $root = new AVLNode($e);
            $this->size++;
        } elseif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素
            $root->left = $this->recursionAdd($root->left, $e);
        } elseif ($e > $root->e) { //若元素大于当前节点元素 则向右节点递归添加元素
            $root->right = $this->recursionAdd($root->right, $e);
        } //若元素等于当前节点元素 则什么都不做

        //更新节点高度
        $root->height = 1 + ($this->getHeight($root->left) > $this->getHeight($root->right) ? $this->getHeight($root->left) : $this->getHeight($root->right));

        //

        $balanceFactor = $this->getBalanceFactor($root);
        if($balanceFactor < -1 || $balanceFactor > 1){ //若平衡因子

        }

        return $root;
    }

    /**
     * 获取节点平衡因子
     * @param AVLNode $node
     * @return int\
     */
    private function getBalanceFactor($node)
    {
        if ($node == null) {
            return 0;
        }
        return $this->getHeight($node->left) - $this->getHeight($node->right);
    }

    /**
     * 判断 AVL 是否包含某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool
    {
        return $this->recursionContains($this->root, $e);
    }

    /**
     * 递归判断 AVL 是否包含某元素
     * @param $root
     * @param $e
     * @return bool
     */
    private function recursionContains($root, $e): bool
    {
        if ($root == null) { //若当前节点为空 则表示不存在元素 $e
            return false;
        } elseif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $e
            return true;
        } elseif ($e < $root->e) { //若 $e 小于当前节点元素，则去左儿子树递归查询是否包含节点
            return $this->recursionContains($root->left, $e);
        } else {  //若 $e 大于当前节点元素，则去右儿子树递归查询是否包含节点
            return $this->recursionContains($root->right, $e);
        }
    }

    /**
     * 前序遍历
     */
    public function preTraversal()
    {
        $this->recursionPreTraversal($this->root, 0);
    }

    /**
     * 前序遍历的递归
     */
    public function recursionPreTraversal($root, $sign_num)
    {
        echo $this->getSign($sign_num);//打印深度
        if ($root == null) {
            echo "null<br>";
            return;
        }
        echo $root->e . "<br>"; //打印当前节点元素
        $this->recursionPreTraversal($root->left, $sign_num + 1);
        $this->recursionPreTraversal($root->right, $sign_num + 1);
    }

    /**
     * 中序遍历
     */
    public function midTraversal()
    {
        $this->recursionMidTraversal($this->root, 0);
    }

    /**
     * 中序遍历的递归
     */
    public function recursionMidTraversal($root, $sign_num)
    {
        if ($root == null) {
            echo $this->getSign($sign_num);//打印深度
            echo "null<br>";
            return;
        }

        $this->recursionMidTraversal($root->left, $sign_num + 1);
        echo $this->getSign($sign_num);//打印深度
        echo $root->e . "<br>";
        $this->recursionMidTraversal($root->right, $sign_num + 1);
    }

    /**
     * 后序遍历
     */
    public function rearTraversal()
    {
        $this->recursionRearTraversal($this->root, 0);
    }

    /**
     * 后序遍历的递归
     */
    public function recursionRearTraversal($root, $sign_num)
    {
        if ($root == null) {
            echo $this->getSign($sign_num);//打印深度
            echo "null<br>";
            return;
        }

        $this->recursionRearTraversal($root->left, $sign_num + 1);
        $this->recursionRearTraversal($root->right, $sign_num + 1);
        echo $this->getSign($sign_num);//打印深度
        echo $root->e . "<br>";
    }

    /**
     * 前序遍历压栈实现
     */
    public function preTraversalByStack()
    {
        $stack = new StackByLinkedList();
        //将根节点压入栈
        $stack->push($this->root);

        while (!$stack->isEmpty()) {
            //出栈
            $node = $stack->pop();
            if ($node != null) { //若出栈的当前节点不是空
                echo $node->e . "<br>"; //先入栈
                //先入栈右儿子
                $stack->push($node->right);
                //然后入栈左儿子
                $stack->push($node->left);
            } else { //若是空
                echo "null<br>";
            }
        }

    }

    /**
     * 中序遍历压栈实现
     */
    public function midTraversalByStack()
    {
        $stack = new StackByLinkedList();
        //将根节点压入栈
        $stack->push($this->root);
        //循环依次出栈
        $node = $stack->pop();

        do {
            if ($node != null) { //若出栈的当前节点不是空
                //先入栈右儿子
                $stack->push($node->right);
                echo $node->e . "<br>"; //然后打印当前节点信息
                //最后入栈左儿子
                $stack->push($node->left);
            } else { //若是空
                echo "null<br>";
            }
            //继续出栈
            $node = $stack->pop();
        } while (!$stack->isEmpty());
    }

    /**
     * 层序遍历实现
     */
    public function tierTraversalByLinkedList()
    {
        $queue = new QueueByLinkedList();
        //将根节点入队
        $queue->enqueue($this->root);
        //循环依次出队
        $node = $queue->dequeue();

        do {
            if ($node != null) { //若出栈的当前节点不是空
                echo $node->e . "<br>"; //然后打印当前节点信息
                $queue->enqueue($node->left);//左儿子入队
                $queue->enqueue($node->right);//右儿子入队
            } else { //若是空
                echo "null<br>";
            }
            //继续出队
            $node = $queue->dequeue();
        } while (!$queue->isEmpty());
    }

    /**
     * 获取最小元素
     * @return mixed
     */
    public function getMin()
    {
        return $this->getMinNode($this->root)->e;
    }

    /**
     * 获取某颗树最小元素节点
     * @param $root
     * @return mixed
     */
    private function getMinNode($root)
    {
        for ($node = $root; $node != null; $node = $node->left) {
            if ($node->left != null) {
                $root = $node->left;
            } else {
                $root = $node;
            }
        }
        return $root;
    }

    /**
     * 获取最大元素
     * @return mixed
     */
    public function getMax()
    {
        return $this->getMaxNode($this->root)->e;
    }

    /**
     * 获取某颗树最大元素节点
     * @param $root
     * @return mixed
     */
    private function getMaxNode($root)
    {
        for ($node = $root; $node != null; $node = $node->right) {
            if ($node->right != null) {
                $root = $node->right;
            } else {
                $root = $node;
            }
        }
        return $root;
    }

    /**
     * 删除 AVL 元素
     * @param $e
     */
    public function remove($e)
    {
        $this->root = $this->recursionRemove($this->root, $e);
    }

    /**
     * 递归删除 AVL 元素
     * @param $root
     * @param $e
     */
    private function recursionRemove($root, $e)
    {
        if ($root != null) {
            if ($e == $root->e) {
                $root = $this->joinRemoveNode($root);
            } elseif ($e < $root->e) {
                $root->left = $this->recursionRemove($root->left, $e);
            } else {
                $root->right = $this->recursionRemove($root->right, $e);
            }
        }
        return $root;
    }

    /**
     * 拼接删除节点 返回新节点
     */
    private function joinRemoveNode($root)
    {

        if ($root->left != null && $root->right == null) {
            $root = $root->left;
        } elseif ($root->left == null && $root->right != null) {
            $root = $root->right;
        } else {
            $leftMax = $this->getMaxNode($root->left);
            $leftMax->right = $root->right;
            $root = $root->left;
        }
        return $root;
    }

    public function getSign($num)
    {
        $str = "";
        for ($i = 0; $i < $num; $i++) {
            $str .= "-----";
        }

        return $str;
    }
}

class AVLNode
{
    public $e;
    public $left = null;
    public $right = null;
    public $height = 1;

    /**
     * 构造函数 初始化节点数据
     * Node constructor.
     * @param $e
     */
    public function __construct($e)
    {
        $this->e = $e;
    }
}